In processing systems, a queue is commonly used to store a backlog of tasks that have been assigned to a unit of the system by other system units. A queue is implemented as memory, or a portion of a memory, in which items of information--queue entries--are stored in the order in which they are received from the task requesting units, and from which they are retrieved in the same order by the task performing unit.
Two implementations of queues are common. One is a first-in, first-out (FIFO) memory, having the property that an item of information loaded into its input register which is located at the tail end of the queue automatically propagates--falls through--empty memory locations toward the output register located at the head end of the queue, and is stored in the first empty location closest to the output register. Retrieval of an item of information from the output register causes all items remaining in the FIFO to shift one location closer to the output register. The other common implementation is a circular buffer having a read and a write pointer associated therewith. The read pointer indicates the location at the head end of the queue from which the next item of information is to be retrieved and the write pointer indicates the location at the tail end of the queue into which the next item of information is to be stored. Retrieval of an item causes the read pointer to point to the next consecutive location that holds information, while storage of an item of information causes the write pointer to point to the next consecutive free location, available for information storage.
In conventional processing systems, task requestors and the task performer are allowed to communicate through the queue only. That is, a task requestor may not transfer a task to the task performer directly, by bypassing the queue, even when the task performer is idle and awaiting receipt of a task. The process of storing a task in the queue, then either propagating it through the FIFO queue or changing the pointers on a circular buffer queue, and finally retrieving a task from queue, takes time, and hence the system is slowed down by these procedures and its performance is adversely affected.
Furthermore in conventional systems, validity checks, such as error checks, on the information intended for queue storage are generally performed before the information is stored in the queue, so that only valid information is stored in the queue. Since queue storage space is generally limited in quantity and hence valuable, this has the desirable property that invalid information does not occupy, and hence waste, valuable queue storage space. Again, however, in the case where the task performer is idle and awaiting receipt of a task, system performance is adversely affected because the task performer must await the results of the validity check, in addition to the above-described delays associated with the queue, before it can begin to process the task.
Finally, should an item of information be invalidated for some reason after it has been stored in the queue of a conventional system, means are generally not provided for immediately removing the invalid information from the queue. Rather, the invalid item of information remains in the queue and occupies valuable queue storage space as any other item until it progresses to the head of the queue and is retrieved therefrom.
In summary, then, conventional queue administration systems are often not efficient in transferring information between devices that store information in the queue and devices that retrieve information from the queue, and in handling validity checks of queue information and disposal of invalid queue information.